package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="https://leetcode.cn/problems/qiu-12n-lcof/">求 1+2+...+n</a>
 * <p>求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。</p>
 * <pre>
 *     示例 1：
 *          输入: n = 3
 *          输出: 6
 *
 *      示例 2：
 *          输入: n = 9
 *          输出: 45
 * </pre>
 * 限制：1 <= n <= 10000
 *
 * @author c2b
 * @since 2023/3/22 10:22
 */
public class JzOffer0064SumNums_M__ {

    /**
     * 迭代。但是题目要求不能使用for关键字
     *
     * @since 2023/3/22 11:09
     */
    public int sumNums(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        System.out.println(sum);
        return sum;
    }

    /**
     * 通过递归实现。通常实现递归的时候我们都会利用条件判断语句来决定递归的出口，但由于题目的限制我们不能使用条件判断语句
     *
     * @since 2023/3/22 11:09
     */
    public int sumNumsByRecursion(int n) {
        return n == 0 ? 0 : n + sumNumsByRecursion(n - 1);
    }

    /**
     * 逻辑运算符的短路性质
     */
    public int sumNumsByRecursion2(int n) {
        final boolean flag = n > 0 && (n += sumNumsByRecursion2(n - 1)) > 0;
        return n;
    }

    /**
     * <b>最优解</b>
     * <p>
     * 快速乘，我们可以将两个数相乘用加法和位运算来模拟，但是可以看到上面的 C++ 实现里我们还是需要循环语句，
     * 有没有办法去掉这个循环语句呢？答案是有的，那就是自己手动展开，因为题目数据范围 n 为 [1,10000]，
     * 所以 n 二进制展开最多不会超过 14 位，我们手动展开 14 层代替循环即可，至此满足了题目的要求
     * </p>
     */
    public int sumNums2(int n) {
        int ans = 0;
        int A = n;
        int B = n + 1;
        boolean flag;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        return ans >> 1;
    }


    public static void main(String[] args) {
        JzOffer0064SumNums_M__ jzOffer0064SumNums_m = new JzOffer0064SumNums_M__();
        int i = jzOffer0064SumNums_m.sumNums2(9193);
        System.out.println(i);
    }
}
